package main

func main() {
	matrix := [][]int{{-1, 3}}
	println(searchMatrix(matrix, 3))
}

/**
 *	searchMatrix
 *	@Description: 二分查找
 *	@param matrix [][]int
 *	@param target int
 *	@return res bool
 */
func searchMatrix(matrix [][]int, target int) (res bool) {
	res = false
	var binSearch func(matri []int, left, right int)
	binSearch = func(matri []int, left, right int) {
		if right-left == 1 {
			if matri[right] == target {
				res = true
				return
			} else if matri[left] == target {
				res = true
				return
			} else {
				return
			}
		}
		mid := (left + right) >> 1
		if matri[mid] == target {
			res = true
			return
		} else if matri[mid] > target {
			binSearch(matri, left, mid)
		} else {
			binSearch(matri, mid, right)
		}
	}
	for i, m := range matrix {
		mL := len(m)
		if matrix[i][0] <= target && matrix[i][mL-1] >= target {
			binSearch(m, 0, mL-1)
		}
		if res {
			return
		}
	}
	return
}
